来自今天模拟赛一道很有意思 的题
关于HACK
之前我也是像一篇题解一样的做法，但是发现这样是错的。
(!mmp[mp[i][j]][mp[frx][fry]])
这一句话的判断又明显的问题，如果之前已经在左上角配过了两种颜色，
但同样的颜色配对在右下角的联通块大于左上角，但因为左上角已经搜过了，此时右下角不会搜到。
例如这个数据
5
5 3 5 7 9
3 3 3 2 1
8 9 10 11 12
5 5 5 5 5
3 3 3 3 3
正确答案是10,错解6。
或这个
5
1 1 9 8 8
1 2 7 6 1
5 4 3 2 2
11 10 9 2 1
1 2 1 2 1
正确答案是10,错解4。
更多数据请看讨论
不加这个优化又会TLE，我又不想换算法，那怎么办呢
于是在此提供一种比较难叉掉的随机算法
（欢迎大家来叉掉）
题解
首先大家都知道这题是个暴力搜索，第一问很简单，直接对于每个点暴力dfs
关键是第二问，我们如何找到两种颜色来bfs
- 1.我会枚举
既然已经说了前面一种优化是错的
所以我们就直接暴力枚举不考虑颜色。。
于是可以获得TLE一个点的好成绩
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N=300;
const int M=1e6+10;
int mp[N][N],ans2,n,m,ans,col[M],tmp,ans1;
bool vis[N][N],flag[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
map<int,bool>match[M];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs(int x,int y)
{
vis[x][y]=1;
tmp++;
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(!tx||!ty||tx>n||ty>n||vis[tx][ty])continue;
if(mp[tx][ty]==mp[x][y])dfs(tx,ty);
}
}
struct point
{
int x,y;
};
void bfs(int stx,int sty,int sttx,int stty)//直接暴力bfs
{
tmp=1;
memset(flag,0,sizeof(flag));//其实这里还可以优化
queue<point>q;
q.push((point){stx,sty});
flag[stx][sty]=1;
while(!q.empty())
{
int x=q.front().x,y=q.front().y;
q.pop();
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(!tx||!ty||tx>n||ty>n||flag[tx][ty])continue;
if(mp[tx][ty]!=mp[stx][sty]&&mp[tx][ty]!=mp[sttx][stty])continue;
tmp++;
flag[tx][ty]=1;
q.push((point){tx,ty});
}
}
ans2=max(ans2,tmp);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!vis[i][j])tmp=0,dfs(i,j),col[mp[i][j]]=max(col[mp[i][j]],tmp),ans1=max(ans1,col[mp[i][j]]);
printf("%d\n",ans1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
for(int k=0;k<4;k++)
{
int tx=i+dx[k];
int ty=j+dy[k];
if(!tx||!ty||tx>n||ty>n||mp[tx][ty]==mp[i][j])continue;
bfs(i,j,tx,ty);//每次暴力找周边的点进行bfs
}
}
printf("%d",ans2);
return 0;
}
- 2.我会随机化
基于之前的枚举，我们加入随机化操作。
1.我会rand_shuffle
之前是从头枚举到尾，这一次我们用rand_shuffle随机一个排列，按这个顺序进行bfs
我们惊奇的发现，成功A掉了这题，包括hack的数据！！！
当然我们还要加入卡时间操作
第一种随机化操作，正确性还是比较高的
pair<int,int>rak[N*N];
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
rak[++cnt]=make_pair(i,j);
random_shuffle(rak+1,rak+1+cnt);
int t=1;
while (t <= cnt && t <= n * n && (double)clock() / CLOCKS_PER_SEC < 0.9)
{
int i=rak[t].first,j=rak[t].second;
for(int k=0;k<4;k++)
{
int tx=i+dx[k];
int ty=j+dy[k];
if(!tx||!ty||tx>n||ty>n||mp[tx][ty]==mp[i][j])continue;
bfs(i,j,tx,ty);
}
t++;
}
2.我还会直接暴力rand()
我们不用rand_shuffle一个顺序，直接每次rand两个点，
虽然有rand到两个相同点的机率，但是这样被叉掉 的机率很高
还是rand_shuffle更优秀
srand(unsigned(time(NULL)));
for(int s=1;s<=60000;s++)
{
if( (double)clock() / CLOCKS_PER_SEC >= 0.9)break;
int i=rand()%n+1,j=rand()%n+1;
for(int k=0;k<4;k++)
{
int tx=i+dx[k];
int ty=j+dy[k];
if(!tx||!ty||tx>n||ty>n||mp[tx][ty]==mp[i][j])continue;
bfs(i,j,tx,ty);
}
}
- 3.我还会时间戳优化
我们发现在每次bfs的过程中其实没必要每次都memset一下，
把flag变成int类型，增加一个时间变量TIM_CNT
void bfs(int stx,int sty,int sttx,int stty)
{
tmp=1;
TIM_CNT++;//时间戳优化
queue<point>q;
q.push((point){stx,sty});
flag[stx][sty]=TIM_CNT;
while(!q.empty())
{
int x=q.front().x,y=q.front().y;
q.pop();
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(!tx||!ty||tx>n||ty>n||flag[tx][ty]==TIM_CNT)continue;
if(mp[tx][ty]!=mp[stx][sty]&&mp[tx][ty]!=mp[sttx][stty])continue;
tmp++;
flag[tx][ty]=TIM_CNT;//把flag赋值为当前时间
q.push((point){tx,ty});
}
}
ans2=max(ans2,tmp);
}
我们会发现这样就又快了接近1000ms，是真的非常有用
至此，我们发现随机化真的难卡掉，可以说除了慢了一些真的非常优秀。